//给定字符串 s 和 t ，判断 s 是否为 t 的子序列。 
//
// 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而
//"aec"不是）。 
//
// 进阶： 
//
// 如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代
//码？ 
//
// 致谢： 
//
// 特别感谢 @pbrother 添加此问题并且创建所有测试用例。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "abc", t = "ahbgdc"
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：s = "axc", t = "ahbgdc"
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// 0 <= s.length <= 100 
// 0 <= t.length <= 10^4 
// 两个字符串都只由小写字符组成。 
// 
// Related Topics 双指针 字符串 动态规划 👍 643 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class IsSubsequence {
    public static void main(String[] args) {
        Solution solution = new IsSubsequence().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean isSubsequence(String s, String t) {
            // dp[i][j]表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]
            int[][] dp = new int[s.length() + 1][t.length() + 1];
            // 初始化左上两边
            for (int i = 0; i < s.length() + 1; i++) {
                dp[i][0] = 0;
            }

            for (int i = 0; i < t.length() + 1; i++) {
                dp[0][i] = 0;
            }

            for (int i = 1; i < s.length() + 1; i++) {
                for (int j = 1; j < t.length() + 1; j++) {
//                    if (s[i - 1] == t[j - 1])
//                        t中找到了一个字符在s中也出现了
//                    if (s[i - 1] != t[j - 1])
//                        相当于t要删除元素，继续匹配
                    if (s.charAt(i - 1) == t.charAt(j - 1)) {
                        dp[i][j] = dp[i - 1][j - 1] + 1; // 相同子序列数加一，表示s中又有一个字母在t中
                    } else {
                        dp[i][j] = dp[i][j - 1];    // 不相等时，子序列的长度不变
                    }
                }
            }

            return dp[s.length()][t.length()] == s.length() ? true : false;
        }

        // 二分搜索来判断
        // https://labuladong.gitee.io/algo/4/33/133/
        /*public boolean isSubsequence(String s, String t) {
            int m = s.length(), n = t.length();
            // 保存t中字符的所以位置
            ArrayList<Integer>[] index = new ArrayList[256];
            for (int i = 0; i < n; i++) {
                char c = t.charAt(i);
                if (index[c] == null) {
                    index[c] = new ArrayList<>();
                }
                index[c].add(i);
            }

            // 注意是对索引位置进行搜索
            int j = 0; // 串 t 上的指针
            for (int i = 0; i < m; i++) {
                char c = s.charAt(i);
                // 整个 t 压根儿没有字符 c
                if (index[c] == null) return false;
                int pos = findLeft(index[c], j);
                // 搜到到达最后都没有，返回false
                if (pos == index[c].size()) return false;
                // 更新索引
                j = index[c].get(pos) + 1;
            }

            return true;
        }

        // 找到左边的元素
        public int findLeft(List<Integer> list, int val) {
            int i = 0, j = list.size();
            while (i < j) {
                int m = i + (j - i) / 2;
                if (list.get(m) < val) {
                    i = m + 1;
                } else {
                    j = m;
                }
            }

            return i;
        }*/

    }
//leetcode submit region end(Prohibit modification and deletion)

}
